Different ways to add parentheses

Time: O(Nx4N/N(3/2)); Space: O(Nx4N/N(3/2)); medium

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators.

The valid operators are +, - and *.

Example 1:

Input: input = “2-1-1”

Output: [0, 2]

Explanation: * ((2-1)-1) = 0 * (2-(1-1)) = 2

Example 2:

Input: input = “2 * 3 - 4 * 5”

Output: [-34, -14, -10, -10, 10]

Explanation:

• (2(3-(45))) = -34

• ((23)-(45)) = -14

• ((2(3-4))5) = -10

• (2((3-4)5)) = -10

• (((23)-4)5) = 10

import operator
import re

class Solution1(object):
    """
    Time: O(n * 4^n / n^(3/2)) ~= n * Catalan numbers = n * (C(2n, n) - C(2n, n - 1)),
          due to the size of the results is Catalan numbers,
          and every way of evaluation is the length of the string,
          so the time complexity is at most n * Catalan numbers.
    Space: O(n * 4^n / n^(3/2)), the cache size of lookup is at most n * Catalan numbers.

    """
    def diffWaysToCompute(self, input):
        """
        :type input: string
        :rtype: List[int]
        """
        tokens = re.split('(\D)', input)
        nums = list(map(int, tokens[::2]))
        ops = list(map({'+': operator.add, '-': operator.sub, '*': operator.mul}.get, tokens[1::2]))
        lookup = [[None for _ in range(len(nums))] for _ in range(len(nums))]

        def diffWaysToComputeRecu(left, right):
            if left == right:
                return [nums[left]]
            if lookup[left][right]:
                return lookup[left][right]

            lookup[left][right] = [ops[i](x, y)
                                   for i in range(left, right)
                                   for x in diffWaysToComputeRecu(left, i)
                                   for y in diffWaysToComputeRecu(i + 1, right)]
            return lookup[left][right]

        return diffWaysToComputeRecu(0, len(nums) - 1)

s = Solution1()

input = "2-1-1"
# print(s.diffWaysToCompute(input))
assert s.diffWaysToCompute(input) == [0, 2] or [2, 0]

input = "2*3-4*5"
# print(s.diffWaysToCompute(input))       # [-34, -10, -14, -10, 10]
assert s.diffWaysToCompute(input) == [-34, -14, -10, -10, 10] or [-34, -10, -14, -10, 10]

class Solution2(object):
    def diffWaysToCompute(self, input):
        """
        :type input: string
        :rtype: List[int]
        """
        lookup = [[None for _ in range(len(input) + 1)] for _ in range(len(input) + 1)]
        ops = {'+': operator.add, '-': operator.sub, '*': operator.mul}

        def diffWaysToComputeRecu(left, right):
            if lookup[left][right]:
                return lookup[left][right]
            result = []
            for i in range(left, right):
                if input[i] in ops:
                    for x in diffWaysToComputeRecu(left, i):
                        for y in diffWaysToComputeRecu(i + 1, right):
                            result.append(ops[input[i]](x, y))

            if not result:
                result = [int(input[left:right])]
            lookup[left][right] = result
            return lookup[left][right]

        return diffWaysToComputeRecu(0, len(input))

s = Solution2()

input = "2-1-1"
assert s.diffWaysToCompute(input) == [0, 2] or [2, 0]

input = "2*3-4*5"
# print(s.diffWaysToCompute(input))   # [-34, -10, -14, -10, 10]
assert s.diffWaysToCompute(input) == [-34, -14, -10, -10, 10] or [-34, -10, -14, -10, 10]

See also:

https://leetcode.com/problems/different-ways-to-add-parentheses

https://www.lintcode.com/problem/different-ways-to-add-parentheses/description